---
id: unit2
title: 第二章  命题逻辑的推理理论
---


2.1 范式

一个简单析取式是重言式，当且仅当它同时含某个命题变元及它的否定式。一个简单合取式是矛盾式，当且仅当它同时含某个命题变元及它的否定式。

合取范式是由简单析取式的合取构成的；析取范式是由简单合取式的析取构成的。

［计算］求等值合取范式或析取范式的步骤。

（1）任何公式都可变换为仅含联结词完备集｛一，A，V｝中的联结词的公式。利用等价等值式A→B（A→B）A（B→A）与蕴涵等值式A→B→～AVB，可以消去公式中出现的联结词→和→。

（2）利用双重否定律--AA和德摩根律-（AAB）-AV-B、（AVB）AA-B进行等值变换，保证在范式中不出现形如--A、（AAB）、～（AV B）这样的子公式，实际上，使用德摩根律是让否定联结词一出现在命题变元的前面，而不是括号的前面。

（3）利用分配律AA（BVC）（AΛB） V （AΛC）、AV（BAC）＝（AVB）Λ（AV C）进行等值变换，保证在析取范式中不出现形如AA（BVC）的子公式，在合取范式中不出现形如AV（BAC）的子公式。

［单选、填空、计算］小项。

1．小项的定义

n个命题变元的简单合取式，称作布尔合取或极小项，简称为小项。

一般来说，n个命题变元P1，P2，·．．，Pn共有2&quot;个小项。为了表示的更直观，我们以字母m加上由编码构成的下标来表示每个小项，其中下标是一个n位的二进制数。为了简单起见，有时也用n位二进制对应的十进制数i来表示小项的编码。

2．小项的性质

（1）每个小项具有一个相应编码，且只在一种情况下真值为T，即按照其编码值进行指派时，其真值为T，其他情况下，真值都为F。故每个小项有一个成真赋值，有2＂-1种成假赋值。每个小项的成真赋值均不相同。


第2章命题逻辑的推理理论

5

·6· 离散数学


（2）任意两个不同小项的合取式为矛盾式。

（3）全体小项的析取式为重言式：

2&quot;-1

m;=mo V miV··Vm2&quot;-1→T。

i=0

［单选、填空、计算］大项。

1．大项的定义

n个命题变元的简单析取式，称作布尔析取或极大项，简称为大项。

与小项情况类似，对每个大项也可以进行编码。以字母M加上由编码构成的下标来表示每个大项，其中下标是一个n位的二进制数。

2．大项的性质

（1）每个大项具有一个相应编码，且只在一种情况下真值为F，即按照其编码值进行指派时，其真值为F，其他情况下，真值都为T。故每个大项有一个成假赋值，有2＂-1种成真赋值。每个大项的成假赋值均不相同。

（2）任意两个不同大项的析取式为重言式。

（3）全体大项的合取式为矛盾式：

2&quot;-1

M;=MoΛM1Λ··ΛM2&quot;-1→F。

i=0

2.2 主范式

［计算］主析取范式。

在公式的真值表中，所有真值为T的指派所对应的小项的析取，即构成该公式的主析取范式。

除了采用真值表法可求合式公式的主析取范式外，还可采用等值演算方法求解。步骤如下：

（1）采用求等值析取范式的步骤，求得与所给公式等值的简单合取式的析取式。

（2）若某简单合取式中没有包含所有的变元，则需要根据排中律P；V-PT、同一律AATA和分配律进行变换。例如，某简单合取式A；中缺少变元P1，则通过如下的变换：

A;A(P;V→P;)=(A;AP;)V(A:A-P;)

可使简单合取式A；中增加P；或-Pi。

第2章命题逻辑的推理理论 ·7


（3）去掉重复出现的小项。

［计算］主合取范式。

在公式的真值表中，所有真值为F的指派所对应的大项的合取，即为此公式的主合取范式。

求命题公式A的主合取范式有两种方法：方法一是采用真值表法，求出所有真值为F的大项，并求它们的合取即可；方法二是采用等值演算方法。

［单选、填空、计算］主析取范式和主合取范式的关系。

若命题公式A中含有n个命题变元，且A的主析取范式中含有k个小项mi1，m2，，mu，则A的主合取范式必含有2&quot;-k个大项。如果命题公式A的主析取范式为： (i1,i2,··，），则A的主合取范式为：

IΠ(0,1,2,·,i1-1,i1+1,··,i2-1,i2+1,·,-1,ik+1,··,2&quot;-1)。

从A的主析取范式求其主合取范式步骤为：

（1）求出A的主析取范式中未包含小项的下标。

（2）把（1）中求出的&quot;下标&quot;写成对应大项。

（3）将（2）中得到的大项进行合取，即为A的主合取范式。

2.3 自然推理系统

判别有效结论的过程就是论证过程，可采用真值表法、主范式方法和推理法。

［计算、证明、综合应用］常用的等值公式表（表2.1）和推理定律表（表2.2）。

表2.1 等值公式表

| E1 | A--A |
| --- | --- |
| E2 | AABBAA |
| E3 | AVBBVA |
| E4 | (AAB)ACAA(BAC) |
| Es | (AV B)V C→AV(BVC) |
| E6 | ΑΛ(BVC)=(AAB)V(AAC) |
| E7 | AV(BAC)=(AVB)A(AVC) |
| E8 | -(AAB)-AV-B |
| E9 | -(AV B)-AA-B |
| E10 | AAVA |


（续表）

| E11AAAA |
| --- |
| E12 | AV(BA→B)A |
| E13 | AA(BV-B)A |
| E14 | AV(BV→B)→T |
| E15 | AA(BA-B)F |
| E16 | A→B→AVB |
| E17 | =(A→B)AΛB |
| E18 | A→B-B→-A |
| E19 | A→(B→C)=(AAB)→C |
| E20 | A→B(A→B)A(B→A) |
| E21 | A→B(AAB)V(-AΛ-B) |
| E22 | -(A→B)A→-B |

表2.2 推理定律表

| 11 | AAB→A |
| --- | --- |
| 1 | AAB→B |
| I3 | A→AV B |
| 14 | B→AVB |
| I5 | -A→A→B |
| I6 | B→-A→B |
| I7 | -(A→B)A |
| 18 | J(A-B)ルB |
| I9 | A,BAAB |
| I10 | -A,AV B→B |
| I11 | A,A→B→B |
| I12 | -B,A→B→-A |
| 113 | A→B,B→C→A→C |
| I14 |
 |
|
 | AV B,A→C,B→C→C |
| 115 |
 |
|
 | A→B=(AVC)→(BV C) |
| 116 |
 |
| A→B→(AAC)→(BAC) |


·8·


［证明、综合应用］常用的推理规则。

（1）前提引入规则：在证明的任何步骤上，都可以引入前提，简称P规则。

（2）结论引入规则：在证明的任何步骤上，所证明的结论都可作为后续证明的前提，称为T规则。

（3）转换规则：在证明的任何步骤上，命题公式中的任何子命题公式都可以用与之等值的命题公式置换，也称为T规则。
